; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt < %s -passes=jump-threading -S | FileCheck %s
; RUN: opt < %s -aa-pipeline=basic-aa -passes=jump-threading -S | FileCheck %s

target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128"
target triple = "i386-apple-darwin7"

; Test that we can thread through the block with the partially redundant load (%2).
; rdar://6402033
define i32 @test1(ptr %P) nounwind {
; CHECK-LABEL: @test1(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[TMP0:%.*]] = tail call i32 (...) @f1() #[[ATTR0:[0-9]+]]
; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 0
; CHECK-NEXT:    br i1 [[TMP1]], label [[BB1:%.*]], label [[BB1_THREAD:%.*]]
; CHECK:       bb1.thread:
; CHECK-NEXT:    store i32 42, ptr [[P:%.*]], align 4
; CHECK-NEXT:    br label [[BB3:%.*]]
; CHECK:       bb1:
; CHECK-NEXT:    [[DOTPR:%.*]] = load i32, ptr [[P]], align 4
; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i32 [[DOTPR]], 36
; CHECK-NEXT:    br i1 [[TMP2]], label [[BB3]], label [[BB2:%.*]]
; CHECK:       bb2:
; CHECK-NEXT:    [[TMP3:%.*]] = tail call i32 (...) @f2() #[[ATTR0]]
; CHECK-NEXT:    ret i32 0
; CHECK:       bb3:
; CHECK-NEXT:    [[RES_02:%.*]] = phi i32 [ 1, [[BB1_THREAD]] ], [ 0, [[BB1]] ]
; CHECK-NEXT:    ret i32 [[RES_02]]
;
entry:
  %0 = tail call i32 (...) @f1() nounwind		; <i32> [#uses=1]
  %1 = icmp eq i32 %0, 0		; <i1> [#uses=1]
  br i1 %1, label %bb1, label %bb

bb:		; preds = %entry
  store i32 42, ptr %P, align 4
  br label %bb1

bb1:		; preds = %entry, %bb
  %res.0 = phi i32 [ 1, %bb ], [ 0, %entry ]		; <i32> [#uses=2]
  %2 = load i32, ptr %P, align 4		; <i32> [#uses=1]
  %3 = icmp sgt i32 %2, 36		; <i1> [#uses=1]
  br i1 %3, label %bb3, label %bb2

bb2:		; preds = %bb1
  %4 = tail call i32 (...) @f2() nounwind		; <i32> [#uses=0]
  ret i32 %res.0

bb3:		; preds = %bb1
  ret i32 %res.0
}

declare i32 @f1(...)

declare i32 @f2(...)


;; Check that we preserve TBAA information.
; rdar://11039258

define i32 @test2(ptr %P) nounwind {
; CHECK-LABEL: @test2(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[TMP0:%.*]] = tail call i32 (...) @f1() #[[ATTR0]]
; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 0
; CHECK-NEXT:    br i1 [[TMP1]], label [[BB1:%.*]], label [[BB1_THREAD:%.*]]
; CHECK:       bb1.thread:
; CHECK-NEXT:    store i32 42, ptr [[P:%.*]], align 4, !tbaa [[TBAA0:![0-9]+]]
; CHECK-NEXT:    br label [[BB3:%.*]]
; CHECK:       bb1:
; CHECK-NEXT:    [[DOTPR:%.*]] = load i32, ptr [[P]], align 4, !tbaa [[TBAA0]]
; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i32 [[DOTPR]], 36
; CHECK-NEXT:    br i1 [[TMP2]], label [[BB3]], label [[BB2:%.*]]
; CHECK:       bb2:
; CHECK-NEXT:    [[TMP3:%.*]] = tail call i32 (...) @f2() #[[ATTR0]]
; CHECK-NEXT:    ret i32 0
; CHECK:       bb3:
; CHECK-NEXT:    [[RES_02:%.*]] = phi i32 [ 1, [[BB1_THREAD]] ], [ 0, [[BB1]] ]
; CHECK-NEXT:    ret i32 [[RES_02]]
;
entry:
  %0 = tail call i32 (...) @f1() nounwind		; <i32> [#uses=1]
  %1 = icmp eq i32 %0, 0		; <i1> [#uses=1]
  br i1 %1, label %bb1, label %bb

bb:		; preds = %entry
  store i32 42, ptr %P, align 4, !tbaa !0
  br label %bb1

bb1:		; preds = %entry, %bb
  %res.0 = phi i32 [ 1, %bb ], [ 0, %entry ]
  %2 = load i32, ptr %P, align 4, !tbaa !0
  %3 = icmp sgt i32 %2, 36
  br i1 %3, label %bb3, label %bb2

bb2:		; preds = %bb1
  %4 = tail call i32 (...) @f2() nounwind
  ret i32 %res.0

bb3:		; preds = %bb1
  ret i32 %res.0
}

define i32 @test3(ptr %x, i1 %f) {
; Correctly thread loads of different (but compatible) types, placing bitcasts
; as necessary in the predecessors. This is especially tricky because the same
; predecessor ends up with two entries in the PHI node and they must share
; a single cast.
; CHECK-LABEL: @test3(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[TMP1:%.*]] = load ptr, ptr [[X:%.*]], align 8
; CHECK-NEXT:    br i1 [[F:%.*]], label [[IF_END57:%.*]], label [[IF_END57]]
; CHECK:       if.end57:
; CHECK-NEXT:    [[TMP3:%.*]] = phi ptr [ [[TMP1]], [[ENTRY:%.*]] ], [ [[TMP1]], [[ENTRY]] ]
; CHECK-NEXT:    [[TOBOOL59:%.*]] = icmp eq ptr [[TMP3]], null
; CHECK-NEXT:    br i1 [[TOBOOL59]], label [[RETURN:%.*]], label [[IF_THEN60:%.*]]
; CHECK:       if.then60:
; CHECK-NEXT:    ret i32 42
; CHECK:       return:
; CHECK-NEXT:    ret i32 13
;
entry:
  %0 = load ptr, ptr %x, align 8
  br i1 %f, label %if.end57, label %if.then56

if.then56:
  br label %if.end57

if.end57:
  %1 = load ptr, ptr %x, align 8
  %tobool59 = icmp eq ptr %1, null
  br i1 %tobool59, label %return, label %if.then60

if.then60:
  ret i32 42

return:
  ret i32 13
}

define i32 @test4(ptr %P) {
; CHECK-LABEL: @test4(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[V0:%.*]] = tail call i32 (...) @f1()
; CHECK-NEXT:    [[V1:%.*]] = icmp eq i32 [[V0]], 0
; CHECK-NEXT:    br i1 [[V1]], label [[BB1:%.*]], label [[BB1_THREAD:%.*]]
; CHECK:       bb1.thread:
; CHECK-NEXT:    store atomic i32 42, ptr [[P:%.*]] unordered, align 4
; CHECK-NEXT:    br label [[BB3:%.*]]
; CHECK:       bb1:
; CHECK-NEXT:    [[V2_PR:%.*]] = load atomic i32, ptr [[P]] unordered, align 4
; CHECK-NEXT:    [[V3:%.*]] = icmp sgt i32 [[V2_PR]], 36
; CHECK-NEXT:    br i1 [[V3]], label [[BB3]], label [[BB2:%.*]]
; CHECK:       bb2:
; CHECK-NEXT:    [[V4:%.*]] = tail call i32 (...) @f2()
; CHECK-NEXT:    ret i32 0
; CHECK:       bb3:
; CHECK-NEXT:    [[RES_04:%.*]] = phi i32 [ 1, [[BB1_THREAD]] ], [ 0, [[BB1]] ]
; CHECK-NEXT:    ret i32 [[RES_04]]
;
entry:
  %v0 = tail call i32 (...) @f1()
  %v1 = icmp eq i32 %v0, 0
  br i1 %v1, label %bb1, label %bb

bb:
  store atomic i32 42, ptr %P unordered, align 4
  br label %bb1

bb1:
  %res.0 = phi i32 [ 1, %bb ], [ 0, %entry ]
  %v2 = load atomic i32, ptr %P unordered, align 4
  %v3 = icmp sgt i32 %v2, 36
  br i1 %v3, label %bb3, label %bb2

bb2:
  %v4 = tail call i32 (...) @f2()
  ret i32 %res.0

bb3:
  ret i32 %res.0
}

define i32 @test5(ptr %P) {
; Negative test
; CHECK-LABEL: @test5(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[V0:%.*]] = tail call i32 (...) @f1()
; CHECK-NEXT:    [[V1:%.*]] = icmp eq i32 [[V0]], 0
; CHECK-NEXT:    br i1 [[V1]], label [[BB1:%.*]], label [[BB:%.*]]
; CHECK:       bb:
; CHECK-NEXT:    store atomic i32 42, ptr [[P:%.*]] release, align 4
; CHECK-NEXT:    br label [[BB1]]
; CHECK:       bb1:
; CHECK-NEXT:    [[RES_0:%.*]] = phi i32 [ 1, [[BB]] ], [ 0, [[ENTRY:%.*]] ]
; CHECK-NEXT:    [[V2:%.*]] = load atomic i32, ptr [[P]] acquire, align 4
; CHECK-NEXT:    [[V3:%.*]] = icmp sgt i32 [[V2]], 36
; CHECK-NEXT:    br i1 [[V3]], label [[BB3:%.*]], label [[BB2:%.*]]
; CHECK:       bb2:
; CHECK-NEXT:    [[V4:%.*]] = tail call i32 (...) @f2()
; CHECK-NEXT:    ret i32 [[RES_0]]
; CHECK:       bb3:
; CHECK-NEXT:    ret i32 [[RES_0]]
;
entry:
  %v0 = tail call i32 (...) @f1()
  %v1 = icmp eq i32 %v0, 0
  br i1 %v1, label %bb1, label %bb

bb:
  store atomic i32 42, ptr %P release, align 4
  br label %bb1

bb1:

  %res.0 = phi i32 [ 1, %bb ], [ 0, %entry ]
  %v2 = load atomic i32, ptr %P acquire, align 4
  %v3 = icmp sgt i32 %v2, 36
  br i1 %v3, label %bb3, label %bb2

bb2:
  %v4 = tail call i32 (...) @f2()
  ret i32 %res.0

bb3:
  ret i32 %res.0
}

define i32 @test6(ptr %P) {
; Negative test
; CHECK-LABEL: @test6(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[V0:%.*]] = tail call i32 (...) @f1()
; CHECK-NEXT:    [[V1:%.*]] = icmp eq i32 [[V0]], 0
; CHECK-NEXT:    br i1 [[V1]], label [[BB1:%.*]], label [[BB:%.*]]
; CHECK:       bb:
; CHECK-NEXT:    store i32 42, ptr [[P:%.*]], align 4
; CHECK-NEXT:    br label [[BB1]]
; CHECK:       bb1:
; CHECK-NEXT:    [[RES_0:%.*]] = phi i32 [ 1, [[BB]] ], [ 0, [[ENTRY:%.*]] ]
; CHECK-NEXT:    [[V2:%.*]] = load atomic i32, ptr [[P]] acquire, align 4
; CHECK-NEXT:    [[V3:%.*]] = icmp sgt i32 [[V2]], 36
; CHECK-NEXT:    br i1 [[V3]], label [[BB3:%.*]], label [[BB2:%.*]]
; CHECK:       bb2:
; CHECK-NEXT:    [[V4:%.*]] = tail call i32 (...) @f2()
; CHECK-NEXT:    ret i32 [[RES_0]]
; CHECK:       bb3:
; CHECK-NEXT:    ret i32 [[RES_0]]
;
entry:
  %v0 = tail call i32 (...) @f1()
  %v1 = icmp eq i32 %v0, 0
  br i1 %v1, label %bb1, label %bb

bb:
  store i32 42, ptr %P
  br label %bb1

bb1:

  %res.0 = phi i32 [ 1, %bb ], [ 0, %entry ]
  %v2 = load atomic i32, ptr %P acquire, align 4
  %v3 = icmp sgt i32 %v2, 36
  br i1 %v3, label %bb3, label %bb2

bb2:
  %v4 = tail call i32 (...) @f2()
  ret i32 %res.0

bb3:
  ret i32 %res.0
}

define i32 @test7(ptr %P) {
; Negative test
; CHECK-LABEL: @test7(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[V0:%.*]] = tail call i32 (...) @f1()
; CHECK-NEXT:    [[V1:%.*]] = icmp eq i32 [[V0]], 0
; CHECK-NEXT:    br i1 [[V1]], label [[BB1:%.*]], label [[BB:%.*]]
; CHECK:       bb:
; CHECK-NEXT:    [[VAL:%.*]] = load i32, ptr [[P:%.*]], align 4
; CHECK-NEXT:    br label [[BB1]]
; CHECK:       bb1:
; CHECK-NEXT:    [[RES_0:%.*]] = phi i32 [ 1, [[BB]] ], [ 0, [[ENTRY:%.*]] ]
; CHECK-NEXT:    [[V2:%.*]] = load atomic i32, ptr [[P]] acquire, align 4
; CHECK-NEXT:    [[V3:%.*]] = icmp sgt i32 [[V2]], 36
; CHECK-NEXT:    br i1 [[V3]], label [[BB3:%.*]], label [[BB2:%.*]]
; CHECK:       bb2:
; CHECK-NEXT:    [[V4:%.*]] = tail call i32 (...) @f2()
; CHECK-NEXT:    ret i32 [[RES_0]]
; CHECK:       bb3:
; CHECK-NEXT:    ret i32 [[RES_0]]
;
entry:
  %v0 = tail call i32 (...) @f1()
  %v1 = icmp eq i32 %v0, 0
  br i1 %v1, label %bb1, label %bb

bb:
  %val = load i32, ptr %P
  br label %bb1

bb1:

  %res.0 = phi i32 [ 1, %bb ], [ 0, %entry ]
  %v2 = load atomic i32, ptr %P acquire, align 4
  %v3 = icmp sgt i32 %v2, 36
  br i1 %v3, label %bb3, label %bb2

bb2:
  %v4 = tail call i32 (...) @f2()
  ret i32 %res.0

bb3:
  ret i32 %res.0
}

; Make sure we merge the aliasing metadata. We keep the range metadata for the
; first load, as it dominates the second load. Hence we can eliminate the
; branch.
define void @test8(ptr, ptr, ptr) {
; CHECK-LABEL: @test8(
; CHECK-NEXT:  ret2:
; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[TMP0:%.*]], align 4, !range [[RNG4:![0-9]+]], !noundef !5
; CHECK-NEXT:    store i32 [[A]], ptr [[TMP1:%.*]], align 4
; CHECK-NEXT:    [[XXX:%.*]] = tail call i32 (...) @f1() #[[ATTR0]]
; CHECK-NEXT:    ret void
;
  %a = load i32, ptr %0, !tbaa !0, !range !4, !alias.scope !9, !noalias !10, !noundef !11
  %b = load i32, ptr %0, !range !5
  store i32 %a, ptr %1
  %c = icmp eq i32 %b, 8
  br i1 %c, label %ret1, label %ret2

ret1:
  ret void

ret2:
  %xxx = tail call i32 (...) @f1() nounwind
  ret void
}

; Make sure we merge/PRE aliasing metadata correctly.  That means that
; we need to remove metadata from the existing load, and add appropriate
; metadata to the newly inserted load.
define void @test9(ptr, ptr, ptr, i1 %c) {
; CHECK-LABEL: @test9(
; CHECK-NEXT:    br i1 [[C:%.*]], label [[D1:%.*]], label [[D2:%.*]]
; CHECK:       d1:
; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[TMP0:%.*]], align 4
; CHECK-NEXT:    br label [[D3:%.*]]
; CHECK:       d2:
; CHECK-NEXT:    [[XXXX:%.*]] = tail call i32 (...) @f1() #[[ATTR0]]
; CHECK-NEXT:    [[B_PR:%.*]] = load i32, ptr [[TMP0]], align 4, !tbaa [[TBAA0]]
; CHECK-NEXT:    br label [[D3]]
; CHECK:       d3:
; CHECK-NEXT:    [[B:%.*]] = phi i32 [ [[B_PR]], [[D2]] ], [ [[A]], [[D1]] ]
; CHECK-NEXT:    [[P:%.*]] = phi i32 [ 1, [[D2]] ], [ [[A]], [[D1]] ]
; CHECK-NEXT:    store i32 [[P]], ptr [[TMP1:%.*]], align 4
; CHECK-NEXT:    [[C2:%.*]] = icmp eq i32 [[B]], 8
; CHECK-NEXT:    br i1 [[C2]], label [[RET1:%.*]], label [[RET2:%.*]]
; CHECK:       ret1:
; CHECK-NEXT:    ret void
; CHECK:       ret2:
; CHECK-NEXT:    [[XXX:%.*]] = tail call i32 (...) @f1() #[[ATTR0]]
; CHECK-NEXT:    ret void
;
  br i1 %c, label %d1, label %d2

d1:
  %a = load i32, ptr %0, !range !4, !alias.scope !9, !noalias !10
  br label %d3

d2:
  %xxxx = tail call i32 (...) @f1() nounwind
  br label %d3

d3:
  %p = phi i32 [ 1, %d2 ], [ %a, %d1 ]
  %b = load i32, ptr %0, !tbaa !0
  store i32 %p, ptr %1
  %c2 = icmp eq i32 %b, 8
  br i1 %c2, label %ret1, label %ret2

ret1:
  ret void

ret2:
  %xxx = tail call i32 (...) @f1() nounwind
  ret void
}

define i32 @fn_noalias(i1 %c2,ptr noalias %P, ptr noalias %P2) {
; CHECK-LABEL: @fn_noalias(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br i1 [[C2:%.*]], label [[COND2:%.*]], label [[COND1:%.*]]
; CHECK:       cond1:
; CHECK-NEXT:    [[L1:%.*]] = load i64, ptr [[P:%.*]], align 4
; CHECK-NEXT:    store i64 42, ptr [[P2:%.*]], align 4
; CHECK-NEXT:    [[C:%.*]] = icmp eq i64 [[L1]], 0
; CHECK-NEXT:    br i1 [[C]], label [[COND2_THREAD:%.*]], label [[END:%.*]]
; CHECK:       cond2.thread:
; CHECK-NEXT:    call void @fn2(i64 [[L1]])
; CHECK-NEXT:    br label [[COND3:%.*]]
; CHECK:       cond2:
; CHECK-NEXT:    [[L2_PR:%.*]] = load i64, ptr [[P]], align 4
; CHECK-NEXT:    call void @fn2(i64 [[L2_PR]])
; CHECK-NEXT:    [[C3:%.*]] = icmp eq i64 [[L2_PR]], 0
; CHECK-NEXT:    br i1 [[C3]], label [[COND3]], label [[END]]
; CHECK:       cond3:
; CHECK-NEXT:    [[L23:%.*]] = phi i64 [ [[L1]], [[COND2_THREAD]] ], [ [[L2_PR]], [[COND2]] ]
; CHECK-NEXT:    call void @fn3(i64 [[L23]])
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    ret i32 0
;
entry:
  br i1 %c2, label %cond2, label %cond1

cond1:
  %l1 = load i64, ptr %P
  store i64 42, ptr %P2
  %c = icmp eq i64 %l1, 0
  br i1 %c, label %cond2, label %end

cond2:
  %l2 = load i64, ptr %P
  call void @fn2(i64 %l2)
  %c3 = icmp eq i64 %l2,  0
  br i1 %c3, label %cond3, label %end

cond3:
  call void @fn3(i64 %l2)
  br label %end

end:
  ret i32 0
}

; This tests if we can thread from %sw.bb.i to %do.body.preheader.i67 through
; %sw.bb21.i. To make this happen, %l2 should be detected as a partically
; redundant load with %l3 across the store to %phase in %sw.bb21.i.

%struct.NEXT_MOVE = type { i32, i32, ptr }
@hash_move = unnamed_addr global [65 x i32] zeroinitializer, align 4
@current_move = internal global [65 x i32] zeroinitializer, align 4
@last = internal unnamed_addr global [65 x ptr] zeroinitializer, align 8
@next_status = internal unnamed_addr global [65 x %struct.NEXT_MOVE] zeroinitializer, align 8
define fastcc i32 @Search(i64 %idxprom.i, i64 %idxprom.i89, i32 %c) {
; CHECK-LABEL: @Search(
; CHECK-NEXT:  cond.true282:
; CHECK-NEXT:    [[ARRAYIDX185:%.*]] = getelementptr inbounds [65 x i32], ptr @hash_move, i64 0, i64 [[IDXPROM_I:%.*]]
; CHECK-NEXT:    [[ARRAYIDX307:%.*]] = getelementptr inbounds [65 x i32], ptr @current_move, i64 0, i64 [[IDXPROM_I]]
; CHECK-NEXT:    [[ARRAYIDX89:%.*]] = getelementptr inbounds [65 x ptr], ptr @last, i64 0, i64 [[IDXPROM_I]]
; CHECK-NEXT:    [[PHASE:%.*]] = getelementptr inbounds [65 x %struct.NEXT_MOVE], ptr @next_status, i64 0, i64 [[IDXPROM_I]], i32 0
; CHECK-NEXT:    switch i32 [[C:%.*]], label [[CLEANUP:%.*]] [
; CHECK-NEXT:    i32 1, label [[SW_BB_I:%.*]]
; CHECK-NEXT:    i32 0, label [[SW_BB21_I:%.*]]
; CHECK-NEXT:    ]
; CHECK:       sw.bb.i:
; CHECK-NEXT:    [[CALL_I62:%.*]] = call fastcc ptr @GenerateCheckEvasions()
; CHECK-NEXT:    store ptr [[CALL_I62]], ptr [[ARRAYIDX89]], align 8
; CHECK-NEXT:    [[L2:%.*]] = load i32, ptr [[ARRAYIDX185]], align 4
; CHECK-NEXT:    [[TOBOOL_I63:%.*]] = icmp eq i32 [[L2]], 0
; CHECK-NEXT:    br i1 [[TOBOOL_I63]], label [[SW_BB21_I_THREAD:%.*]], label [[IF_THEN_I64:%.*]]
; CHECK:       sw.bb21.i.thread:
; CHECK-NEXT:    store i32 10, ptr [[PHASE]], align 8
; CHECK-NEXT:    br label [[DO_BODY_PREHEADER_I67:%.*]]
; CHECK:       if.then.i64:
; CHECK-NEXT:    store i32 7, ptr [[PHASE]], align 8
; CHECK-NEXT:    store i32 [[L2]], ptr [[ARRAYIDX307]], align 4
; CHECK-NEXT:    [[CALL16_I:%.*]] = call fastcc i32 @ValidMove(i32 [[L2]])
; CHECK-NEXT:    [[TOBOOL17_I:%.*]] = icmp eq i32 [[CALL16_I]], 0
; CHECK-NEXT:    br i1 [[TOBOOL17_I]], label [[IF_ELSE_I65:%.*]], label [[CLEANUP]]
; CHECK:       if.else.i65:
; CHECK-NEXT:    call void @f65()
; CHECK-NEXT:    br label [[SW_BB21_I]]
; CHECK:       sw.bb21.i:
; CHECK-NEXT:    [[L3_PR:%.*]] = load i32, ptr [[ARRAYIDX185]], align 4
; CHECK-NEXT:    store i32 10, ptr [[PHASE]], align 8
; CHECK-NEXT:    [[TOBOOL27_I:%.*]] = icmp eq i32 [[L3_PR]], 0
; CHECK-NEXT:    br i1 [[TOBOOL27_I]], label [[DO_BODY_PREHEADER_I67]], label [[CLEANUP]]
; CHECK:       do.body.preheader.i67:
; CHECK-NEXT:    call void @f67()
; CHECK-NEXT:    ret i32 67
; CHECK:       cleanup:
; CHECK-NEXT:    call void @Cleanup()
; CHECK-NEXT:    ret i32 0
;
entry:
  %arrayidx185 = getelementptr inbounds [65 x i32], ptr @hash_move, i64 0, i64 %idxprom.i
  %arrayidx307 = getelementptr inbounds [65 x i32], ptr @current_move, i64 0, i64 %idxprom.i
  %arrayidx89 = getelementptr inbounds [65 x ptr], ptr @last, i64 0, i64 %idxprom.i
  %phase = getelementptr inbounds [65 x %struct.NEXT_MOVE], ptr @next_status, i64 0, i64 %idxprom.i, i32 0
  br label %cond.true282

cond.true282:
  switch i32 %c, label %sw.default.i [
  i32 1, label %sw.bb.i
  i32 0, label %sw.bb21.i
  ]

sw.default.i:
  br label %cleanup

sw.bb.i:
  %call.i62 = call fastcc ptr @GenerateCheckEvasions()
  store ptr %call.i62, ptr %arrayidx89, align 8
  %l2 = load i32, ptr %arrayidx185, align 4
  %tobool.i63 = icmp eq i32 %l2, 0
  br i1 %tobool.i63, label %sw.bb21.i, label %if.then.i64

if.then.i64:                                      ; preds = %sw.bb.i
  store i32 7, ptr %phase, align 8
  store i32 %l2, ptr %arrayidx307, align 4
  %call16.i = call fastcc i32 @ValidMove(i32 %l2)
  %tobool17.i = icmp eq i32 %call16.i, 0
  br i1 %tobool17.i, label %if.else.i65, label %cleanup

if.else.i65:
  call void @f65()
  br label %sw.bb21.i

sw.bb21.i:
  store i32 10, ptr %phase, align 8
  %l3= load i32, ptr %arrayidx185, align 4
  %tobool27.i = icmp eq i32 %l3, 0
  br i1 %tobool27.i, label %do.body.preheader.i67, label %cleanup

do.body.preheader.i67:
  call void @f67()
  ret  i32 67

cleanup:
  call void @Cleanup()
  ret  i32 0
}

declare fastcc ptr @GenerateCheckEvasions()
declare fastcc i32 @ValidMove(i32 %move)
declare void @f67()
declare void @Cleanup()
declare void @f65()

define i32 @fn_SinglePred(i1 %c2,ptr %P) {
; CHECK-LABEL: @fn_SinglePred(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[L1:%.*]] = load i64, ptr [[P:%.*]], align 4
; CHECK-NEXT:    [[C:%.*]] = icmp eq i64 [[L1]], 0
; CHECK-NEXT:    br i1 [[C]], label [[COND3:%.*]], label [[COND1:%.*]]
; CHECK:       cond1:
; CHECK-NEXT:    br i1 [[C2:%.*]], label [[COND2:%.*]], label [[END:%.*]]
; CHECK:       cond2:
; CHECK-NEXT:    [[L2:%.*]] = phi i64 [ [[L1]], [[COND1]] ]
; CHECK-NEXT:    call void @fn2(i64 [[L2]])
; CHECK-NEXT:    br label [[END]]
; CHECK:       cond3:
; CHECK-NEXT:    call void @fn2(i64 [[L1]])
; CHECK-NEXT:    call void @fn3(i64 [[L1]])
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    ret i32 0
;

entry:
  %l1 = load i64, ptr %P
  %c = icmp eq i64 %l1, 0
  br i1 %c, label %cond2, label %cond1

cond1:
  br i1 %c2, label %cond2, label %end

cond2:
  %l2 = load i64, ptr %P
  call void @fn2(i64 %l2)
  %c3 = icmp eq i64 %l2,  0
  br i1 %c3, label %cond3, label %end

cond3:
  call void @fn3(i64 %l2)
  br label %end

end:
  ret i32 0
}

define i32 @fn_SinglePredMultihop(i1 %c1, i1 %c2,ptr %P) {
; CHECK-LABEL: @fn_SinglePredMultihop(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[L1:%.*]] = load i64, ptr [[P:%.*]], align 4
; CHECK-NEXT:    [[C0:%.*]] = icmp eq i64 [[L1]], 0
; CHECK-NEXT:    br i1 [[C0]], label [[COND3:%.*]], label [[COND0:%.*]]
; CHECK:       cond0:
; CHECK-NEXT:    br i1 [[C1:%.*]], label [[COND1:%.*]], label [[END:%.*]]
; CHECK:       cond1:
; CHECK-NEXT:    br i1 [[C2:%.*]], label [[COND2:%.*]], label [[END]]
; CHECK:       cond2:
; CHECK-NEXT:    [[L2:%.*]] = phi i64 [ [[L1]], [[COND1]] ]
; CHECK-NEXT:    call void @fn2(i64 [[L2]])
; CHECK-NEXT:    br label [[END]]
; CHECK:       cond3:
; CHECK-NEXT:    call void @fn2(i64 [[L1]])
; CHECK-NEXT:    call void @fn3(i64 [[L1]])
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    ret i32 0
;

entry:
  %l1 = load i64, ptr %P
  %c0 = icmp eq i64 %l1, 0
  br i1 %c0, label %cond2, label %cond0

cond0:
  br i1 %c1, label %cond1, label %end

cond1:
  br i1 %c2, label %cond2, label %end

cond2:
  %l2 = load i64, ptr %P
  call void @fn2(i64 %l2)
  %c3 = icmp eq i64 %l2,  0
  br i1 %c3, label %cond3, label %end

cond3:
  call void @fn3(i64 %l2)
  br label %end

end:
  ret i32 0
}

declare void @fn2(i64)
declare void @fn3(i64)


; Make sure we phi-translate and make the partially redundant load in
; merge fully redudant and then we can jump-thread the block with the
; store.
;
define i32 @phi_translate_partial_redundant_loads(i32, ptr, ptr) {
; CHECK-LABEL: @phi_translate_partial_redundant_loads(
; CHECK-NEXT:    [[CMP0:%.*]] = icmp ne i32 [[TMP0:%.*]], 0
; CHECK-NEXT:    br i1 [[CMP0]], label [[MERGE_THREAD:%.*]], label [[MERGE:%.*]]
; CHECK:       merge.thread:
; CHECK-NEXT:    store i32 1, ptr [[TMP1:%.*]], align 4
; CHECK-NEXT:    br label [[LEFT_X:%.*]]
; CHECK:       merge:
; CHECK-NEXT:    [[NEWLOAD_PR:%.*]] = load i32, ptr [[TMP2:%.*]], align 4
; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[NEWLOAD_PR]], 5
; CHECK-NEXT:    br i1 [[CMP1]], label [[LEFT_X]], label [[RIGHT_X:%.*]]
; CHECK:       left_x:
; CHECK-NEXT:    ret i32 20
; CHECK:       right_x:
; CHECK-NEXT:    ret i32 10
;
  %cmp0 = icmp ne i32 %0, 0
  br i1 %cmp0, label %left, label %right

left:
  store i32 1, ptr %1, align 4
  br label %merge

right:
  br label %merge

merge:
  %phiptr = phi ptr [ %1, %left ], [ %2, %right ]
  %newload = load i32, ptr %phiptr, align 4
  %cmp1 = icmp slt i32 %newload, 5
  br i1 %cmp1, label %left_x, label %right_x

left_x:
  ret i32 20

right_x:
  ret i32 10
}


; CHECK: [[RNG4]] = !{i32 0, i32 1}

!0 = !{!3, !3, i64 0}
!1 = !{!"omnipotent char", !2}
!2 = !{!"Simple C/C++ TBAA"}
!3 = !{!"int", !1}
!4 = !{ i32 0, i32 1 }
!5 = !{ i32 8, i32 10 }
!6 = !{!6}
!7 = !{!7, !6}
!8 = !{!8, !6}
!9 = !{!7}
!10 = !{!8}
!11 = !{}
